home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1987 / 11 / tracer.c < prev   
C/C++ Source or Header  |  1987-10-08  |  16KB  |  611 lines
  1. /*-----------------------------------------------------------------------
  2.     tracer.c
  3.     
  4.     There is only one externally visible function: find_all_contours
  5.     
  6.     Implements contour search and tracing algorithms
  7.     Some sections are based on Pavlidis, "Algorithms for Graphics and
  8.     Image Processing"
  9.     
  10.     Quick description: the algorithm examines the interiors of known
  11.     contours to find additional contours.
  12.     
  13.     It is started by treating the border of the image itself as a contour.
  14.     
  15.     The final outcome of this algorithm is a tree containing all points
  16.     on contours in the image.  The key for a leaf in the tree is the point
  17.     coordinates.  Each leaf also contains an index for the contour containing
  18.     the point, and the elevation for the point.
  19.     
  20.     William May
  21.     
  22.     created        Jan 31, 1987
  23.     modified    Apr 10, 1987    improve the trace logic to handle
  24.                                 contours that are multiple pixels in
  25.                                 thickness.
  26.   ----------------------------------------------------------------------*/
  27.  
  28.  
  29. #define DEBUG
  30.  
  31. #ifdef DEBUG
  32. #define D(x)    x
  33. #else
  34. #define D(x)
  35. #endif
  36.  
  37. #include <QuickDraw.h>
  38. #include <MemoryMgr.h>
  39. #include <stdio.h>
  40. #include "getpixel.h"
  41. #include "contour.h"
  42. #include "global.h"
  43.  
  44. /* two defines for our trace directions */
  45. #define CLOCKWISE -1
  46. #define COUNTERCLOCKWISE 1
  47.  
  48. /* the index of the image borders is BASE (the exterior contour) */
  49. #define BASE    -1
  50.  
  51. /* define the queue elements */
  52. typedef struct {
  53.     int h, v, chain;
  54. } q_item;
  55.  
  56. static char *qp;            /* pointer to the queue */
  57. static int     qmax = 0;        /* max items in the queue */
  58.  
  59. static int current_elevation = 0;     /* current elevation of region */
  60. static int next_curve = 0;            /* number of next index in curve array */
  61.  
  62. static long point_count;            /* count the points we have found */
  63.  
  64. /*-----------------------------------------------------------------------
  65.     find_all_contours finds all the contours in a bitmap
  66.     first the left side of the bitmap is entered into the queue to
  67.     start off the search.  then each time find_contours returns
  68.     (meaning no more contours at that level) the elevation is incremented
  69.     for the next round of searches.
  70.   -----------------------------------------------------------------------*/
  71. int find_all_contours()
  72. {
  73.     char ch;
  74.     Point pt;
  75.     GrafPtr old_port;
  76.     int draw_point();
  77.     int item;
  78.     register int i;
  79.     char *makequeue();
  80.     
  81.     qp = makequeue(4000, sizeof(q_item));
  82.  
  83.     start_queue();                    /* set up search for exterior of bitmap */
  84.  
  85.     find_contours(BASE);            /* find the first level of contours */
  86.                                     /* parent = -1 */
  87.  
  88.     while (next_point(&item, &pt)) {        /* while there is an unsearched curve */
  89.         trace(pt, COUNTERCLOCKWISE, true);    /* set up queue for next search */
  90.         find_contours(item);                /* go get 'em. item = parent */
  91.     }
  92.  
  93.     free(qp);                        /* all done, get rid of the queue */
  94.     
  95.     set_elevations();                /* set elevations in the array */
  96.     
  97.     printf("max used in queue is %d\n", qmax);
  98.     printf("number of curves found is %d\n", next_curve);
  99.     printf("number of points found is %ld\n", point_count);
  100.     printf("Curve search complete. <cr> to continue: ");
  101.     ch = getchar();
  102.             
  103.     GetPort(&old_port);
  104.     SetPort(right_wind);
  105.     EraseRect(&(right_wind->portRect));
  106.     
  107.     D(printf("Now traversing the tree.\n"));
  108.     D(traverse(root, draw_point));
  109.     
  110.     SetPort(old_port);
  111. }
  112.  
  113. /*----------------------------------------------------------------------
  114.     start_queue puts the left edge of the bitmap into the
  115.     queue to act as start for the bitmap search
  116.     
  117.     only the left edge needs to be put in because the other edges
  118.     would be ignored anyway
  119.   -----------------------------------------------------------------------*/
  120. static start_queue()
  121. {
  122.     register int i;
  123.     q_item q;
  124.     
  125.     q.h = 0;
  126.     q.chain = 6;        /* all starting queue items are going south */
  127.     
  128.     for (i = 0; i < VBITMAX; i++) {
  129.         q.v = i;
  130.         if (!enqueue(&q,qp))
  131.             syserr(0, "Queue overflow in startup function\n");
  132.     }
  133. }
  134.  
  135. /*----------------------------------------------------------------------
  136.     set the next curve starting point if there is one,
  137.     otherwise return 0;
  138.   ----------------------------------------------------------------------*/
  139. static int next_point(item,pt)
  140. int     *item;
  141. Point     *pt;
  142. {
  143.     static int last_searched = -1;    /* last array index used */
  144.             
  145.     if (++last_searched < next_curve) {
  146.         *item = last_searched;
  147.         pt->h = curves[last_searched].p.h;
  148.         pt->v = curves[last_searched].p.v;
  149.         return 1;
  150.     }
  151.     else
  152.         return 0;
  153. }
  154.  
  155. /*----------------------------------------------------------------------
  156.     set the elevations in the array
  157.     assume all contours are ascending
  158.     and increment = 100
  159.   ----------------------------------------------------------------------*/
  160. set_elevations()
  161. {
  162.     register curve_data *p = curves;
  163.     register int parent, i;
  164.     
  165.     for (i = 0; i < next_curve; i++, p++) {
  166.         if ((parent = curves[i].parent) == BASE)
  167.             curves[i].elevation = 100;
  168.         else
  169.             curves[i].elevation = curves[parent].elevation + 100;
  170.     }
  171. }
  172.  
  173. /*-----------------------------------------------------------------------
  174.     find_contours searches for all contours within a closed contour,
  175.     based on the queue elements
  176.     if any are found a non-zero value is returned
  177.   -----------------------------------------------------------------------*/
  178. static int find_contours(parent)
  179. int parent;                        /* index of enclosing curve */
  180. {
  181.     q_item item, *show_next();
  182.     register int c;
  183.     Point p;
  184.     int B, next_chain;
  185.     Point first, last;
  186.                 
  187.     while (dequeue(&item, qp)) {
  188.         c = item.chain;
  189.                 
  190.         if (c == 8) {
  191.             dequeue(&item, qp);
  192.             c = item.chain;
  193.         }
  194.                 
  195.         if ((c >= 5 && c <= 7) ||
  196.             (c == 0 && ((next_chain = (*show_next(qp)).chain) >= 5) &&
  197.             (next_chain <= 7))) {
  198.                 p.h = item.h + 1;
  199.                 p.v = item.v;
  200.             
  201.                 D(first = p);
  202.             
  203.             do {
  204.                 search_x(&B, &p);
  205.                                 
  206.                 if (B == 1) {
  207.  
  208.                     D(last = p);
  209.                     D(show_line(first, last));
  210.  
  211.                     /*
  212.                         if trace found a new contour then break off
  213.                         the scan.  If the point is a new point on a
  214.                         known contour, then continue.
  215.                     */
  216.                     if (trace(p, CLOCKWISE, false)) {
  217.                         /* and add curve to array */
  218.                         curves[next_curve].p = p;
  219.                         curves[next_curve].parent = parent;
  220.                         curves[next_curve].elevation = 0;
  221.                         curves[next_curve].searched = false;
  222.                         next_curve++;
  223.                         break;
  224.                     } else
  225.                         p.h++;    /* bump up to next point */
  226.                 }
  227.                 else if (B >= 2) {
  228.                     D(last = p);
  229.                     D(show_line(first, last));
  230.                     break;
  231.                 }
  232.             } while (1);    
  233.         }
  234.     }    
  235.     return 1;
  236. }
  237.  
  238. /*-----------------------------------------------------------------------
  239.     scan pixels in the x direction at point p
  240.     if the bitmap shows a pixel return 1
  241.     if the bitmap shows a pixel and the pixel is in the tree
  242.     (i.e. the point has been scanned before) return 2
  243.     update the starting point
  244.   -----------------------------------------------------------------------*/
  245. static search_x(b, p)
  246. int *b;
  247. Point *p;
  248. {
  249.     long dcmp();
  250.     /*
  251.         the union makes it easy to use the point coordinates
  252.         as the key in the tree
  253.     */
  254.     union {
  255.         Point pt;
  256.         long  key;
  257.     } q;
  258.     
  259.     q.pt = *p;
  260.     
  261.     if (*b = getpixel(q.pt.h, q.pt.v, &bmap)) {
  262.         if (find(root, q.key, dcmp)) (*b)++;
  263.         return;                            /* don't increment h on a hit */
  264.     }
  265.     
  266.     if (++p->h >= HBITMAX) {
  267.         *b = 2;            /* when we hit the right edge,indicate already found */
  268.         return;
  269.     }
  270. }
  271.  
  272. /*-----------------------------------------------------------------------
  273.     trace traces a contour beginning at the specified point
  274.     at each found point the x,y coordinates and chain code are
  275.     stored both in the queue and the tree.
  276.     
  277.     two result codes are returned:
  278.     0 indicates that the starting point represented a new point on an
  279.       existing (known) contour.  trace was aborted.
  280.     1 indicates a new contour was successfully traced
  281.   -----------------------------------------------------------------------*/
  282. static int trace(p, dir, q_only)
  283. Point p;        /* p is the starting point */
  284. int dir;        /* dir is the trace direction */
  285. Boolean q_only; /*  trace and put in queue only,
  286.                     do not check for dupes in tree */
  287. {
  288.     Point c, t;    /* current point, and transformed point for testing */
  289.     int s;      /* search direction */
  290.     Boolean found, test_pixel();
  291.     int count, used, chain;
  292.     q_item item;
  293.     LEAF *lp, *lp2;
  294.     long icmp(), dcmp();
  295.     GrafPtr old_port;
  296.     union temp {
  297.         long key;
  298.         Point p;
  299.     } temp;
  300.     
  301.     if (dir == COUNTERCLOCKWISE)
  302.         s = 6;
  303.     else
  304.         s = 2;
  305.         
  306.     c = p;
  307.     
  308.     if (q_only) {
  309.         /* has this curve interior been searched before? */
  310.         temp.p.h = c.h;
  311.         temp.p.v = c.v;
  312.         lp = find(root, temp.key, dcmp);
  313.         
  314.         if (curves[lp->curve].searched == true) {
  315.             printf("Curve %d already searched\n", lp->curve);
  316.             return 0;
  317.         }
  318.         else
  319.             curves[lp->curve].searched = true;
  320.             
  321.         item.h = c.h;    /* add data to queue */
  322.         item.v = c.v;
  323.         item.chain = 8;    /* mark beginning of new contour */
  324.         if (!enqueue(&item,qp))
  325.             syserr(0, "Queue overflow in trace\n");
  326.             
  327.         GetPort(&old_port);
  328.         SetPort(right_wind);
  329.         PenPat(white);
  330.         SetPort(old_port);
  331.     }
  332.     else {
  333.         if (!(lp = talloc(sizeof(LEAF))))
  334.             syserr(MemErr, "Insufficient memory for AVL tree");
  335.         else {
  336.             lp->header.p.h = c.h;
  337.             lp->header.p.v = c.v;
  338.             lp->curve = next_curve;
  339.             
  340.             if (lp2 = insert(&root, lp, icmp)) {
  341.                 /* tfree(lp); not implemented in getmem! */
  342.                 return 0;    /* starting point already in the tree !! */
  343.             }
  344.             else {    /* if not in the tree then enqueue the new point */
  345.                 point_count++;
  346.                 
  347.                 item.h = c.h;    /* add data to queue */
  348.                 item.v = c.v;
  349.                 item.chain = 8;    /* mark beginning of new contour */
  350.                 if (!enqueue(&item,qp))
  351.                     syserr(0, "Queue overflow in trace\n");
  352.                         
  353.                 GetPort(&old_port);
  354.                 SetPort(right_wind);
  355.                 PenPat(black);
  356.                 SetPort(old_port);
  357.             }
  358.         }
  359.     }
  360.     
  361.     
  362.     do {
  363.         found = false;
  364.         count = 0;
  365.         while (!found && (count < 3)) {
  366.             count++;
  367.             if (test_pixel(c, add_chain(s, -1 * dir))) {
  368.                 set_pixel(&c, (chain = add_chain(s, -1 * dir)));
  369.                 s = add_chain(s, -2 * dir);
  370.                 found = true;
  371.             }
  372.             else {
  373.                 if (test_pixel(c, s)) {
  374.                     set_pixel(&c, (chain = s));
  375.                     found = true;
  376.                 }
  377.                 else {
  378.                     if (test_pixel(c, add_chain(s, 1 * dir))) {
  379.                         set_pixel(&c, (chain = add_chain(s, 1 * dir)));
  380.                         found = true;
  381.                     }
  382.                     else
  383.                         s = add_chain(s, 2 * dir);
  384.                 }
  385.             }
  386.         }
  387.         D(show_point(c));
  388.         
  389.         if (q_only) {
  390.             item.h = c.h;    /* add data to queue */
  391.             item.v = c.v;
  392.             item.chain = chain;
  393.             if (!enqueue(&item,qp))
  394.                 syserr(0, "Queue overflow in trace\n");
  395.         }
  396.         else {
  397.             if (!(lp = talloc(sizeof(LEAF))))
  398.                 syserr(MemErr, "Insufficient memory for AVL tree");
  399.             else {                
  400.                 lp->header.p.h = c.h;
  401.                 lp->header.p.v = c.v;
  402.                 lp->curve = next_curve;
  403.             
  404.                 if (lp2 = insert(&root, lp, icmp)) {
  405.                     /* tfree(lp); not implemented in getmem! */
  406.                     if ((c.h == p.h) && (c.v == p.v))
  407.                         return 1;    /* we have returned to the start */
  408.                     else
  409.                         return 0;
  410.                 }
  411.                 else {                /* if not in the tree then enqueue point */
  412.                     point_count++;
  413.                     
  414.                     item.h = c.h;    /* add data to queue */
  415.                     item.v = c.v;
  416.                     item.chain = chain;
  417.                     if (!enqueue(&item,qp))
  418.                         syserr(0, "Queue overflow in trace\n");
  419.                 }
  420.             }
  421.         }
  422.         if ((used = sp_used(qp)) > qmax) qmax = used;
  423.         
  424.     } while ((c.h != p.h) || (c.v != p.v));
  425.     
  426.     GetPort(&old_port);
  427.     SetPort(right_wind);
  428.     PenPat(black);
  429.     SetPort(old_port);
  430.     
  431.     return 1;
  432. }
  433.  
  434. /*---------------------------------------------------------------------
  435.     test the s neighbor of point p
  436.   ---------------------------------------------------------------------*/
  437. static Boolean test_pixel(p,s)
  438. Point p;
  439. int s;   /* direction to test */
  440. {
  441.     set_pixel(&p, s);
  442.     return (getpixel(p.h, p.v, &bmap));
  443. }
  444.  
  445. /*----------------------------------------------------------------------
  446.     set point p to point + chain code s
  447.   ----------------------------------------------------------------------*/
  448. static set_pixel(p, s)
  449. Point *p;
  450. int s;
  451. {
  452.     switch (s) {
  453.         case 0:
  454.             (*p).h++;
  455.             break;
  456.         case 1:
  457.             (*p).h++;
  458.             (*p).v--;
  459.             break;
  460.         case 2:
  461.             (*p).v--;
  462.             break;
  463.         case 3:
  464.             (*p).h--;
  465.             (*p).v--;
  466.             break;
  467.         case 4:
  468.             (*p).h--;
  469.             break;
  470.         case 5:
  471.             (*p).h--;
  472.             (*p).v++;
  473.             break;
  474.         case 6:
  475.             (*p).v++;
  476.             break;
  477.         case 7:
  478.             (*p).h++;
  479.             (*p).v++;
  480.             break;
  481.     }
  482. }
  483.  
  484. /*----------------------------------------------------------------------
  485.     add c to chain code s
  486.   ----------------------------------------------------------------------*/
  487. static int add_chain(s,c)
  488. register int s,c;
  489. {
  490.     register int i;
  491.     
  492.     if ((i = s + c) >= 8)
  493.         return (i - 8);
  494.     else {
  495.         if (i < 0)
  496.             return (i + 8);
  497.         else
  498.             return i;
  499.     }
  500. }
  501.  
  502. #ifdef DEBUG
  503.  
  504. /*-----------------------------------------------------------------------
  505.     The code below is used to display the progress of the contour
  506.     analysis in a Macintosh window.  It is obviously totally
  507.     nonportable.  Fixed point arithmetic is used for scaling the MacPaint
  508.     size document to a much smaller window.  Fixed point is much faster
  509.     floating point, and is often used for two and three dimensional
  510.     graphics on the Mac.  This code is for debugging purposes.
  511.   -----------------------------------------------------------------------*/
  512.  
  513. /* ratio is used to scale down picture size by 1/4 */
  514. static Fixed ratio = 0x00004000;
  515.  
  516. /*-----------------------------------------------------------------------
  517.     convert a 16 bit integer to fixed point
  518.   -----------------------------------------------------------------------*/
  519. static Fixed int_to_fix(i)
  520. int i;
  521. {
  522.     asm {
  523.         move.w    i,d0    ; get the number
  524.         ext.l    d0        ; clear top of d0
  525.         swap    d0        ; make it a fixed point number, all done
  526.     }
  527. }
  528.  
  529. /*-----------------------------------------------------------------------
  530.     convert a Fixed point number to 16 bit integer
  531.   -----------------------------------------------------------------------*/
  532. static int fix_to_int(i)
  533. Fixed i;
  534. {
  535.     asm {
  536.         move.l    i,d0        ; get the number
  537.         add.l    #0xA000,d0    ; add .5 to number, for rounding
  538.         swap    d0            ; make the int, ignore upper word of d0
  539.     }
  540. }
  541.  
  542. /*-----------------------------------------------------------------------
  543.     draw the point from a LEAF, scaled down to the actual window size
  544.   -----------------------------------------------------------------------*/
  545. static draw_point(p)
  546. LEAF *p;
  547. {
  548.     GrafPtr oldPort;
  549.     Point q;
  550.     Rect r;
  551.     
  552.     q = p->header.p;
  553.  
  554.     GetPort(&oldPort);
  555.     SetPort(right_wind);
  556.         
  557.     r.top    = fix_to_int(FixMul(int_to_fix(q.v), ratio));
  558.     r.left   = fix_to_int(FixMul(int_to_fix(q.h), ratio));
  559.     r.right  = r.left + 1;
  560.     r.bottom = r.top + 1;
  561.  
  562.     FrameRect(&r);
  563.     SetPort(oldPort);
  564. }
  565.  
  566. /*-----------------------------------------------------------------------
  567.     draw the point, scaled down to the actual window size
  568.   -----------------------------------------------------------------------*/
  569. static show_point(p)
  570. Point p;
  571. {
  572.     GrafPtr oldPort;
  573.     Rect r;
  574.  
  575.     GetPort(&oldPort);
  576.     SetPort(right_wind);
  577.  
  578.     r.top    = fix_to_int(FixMul(int_to_fix(p.v), ratio));
  579.     r.left   = fix_to_int(FixMul(int_to_fix(p.h), ratio));
  580.     r.right  = r.left + 1;
  581.     r.bottom = r.top + 1;
  582.  
  583.     FrameRect(&r);
  584.     SetPort(oldPort);
  585. }
  586.  
  587. /*-----------------------------------------------------------------------
  588.     draw a line, scaled down to the actual window size
  589.   -----------------------------------------------------------------------*/
  590. static show_line(first, last)
  591. Point first,last;
  592. {
  593.     GrafPtr oldPort;
  594.     
  595.     GetPort(&oldPort);
  596.     SetPort(right_wind);
  597.  
  598.     first.v  = fix_to_int(FixMul(int_to_fix(first.v), ratio));
  599.     first.h  = fix_to_int(FixMul(int_to_fix(first.h), ratio));
  600.     
  601.     MoveTo(first.h, first.v);
  602.     
  603.     last.v  = fix_to_int(FixMul(int_to_fix(last.v), ratio));
  604.     last.h  = fix_to_int(FixMul(int_to_fix(last.h), ratio));
  605.         
  606.     LineTo(last.h, last.v);
  607.             
  608.     SetPort(oldPort);
  609. }
  610.  
  611. #endif